package com.cqs.leetcode.dp;

import java.util.function.Function;

/**
 * @author lixiaowen
 * @create 2019-12-28
 */
public class OnesandZeroes474 {

    static class Solution {
        Function<String, Integer> countZeros = s -> {
            int count = 0;
            for (int i = 0; i < s.length(); ++i) {
                if (s.charAt(i) == '0') {
                    ++count;
                }
            }
            return count;
        };

        int[][][] handle = null;

        public int findMaxForm(String[] strs, int m, int n) {
            if (strs == null || strs.length == 0) return 0;
            handle = new int[strs.length][m + 1][n + 1];
            int count = maxForm(strs, 0, m, n);
            return count < 0 ? 0 : count;
        }

        private int maxForm(String[] strs, int index, int m, int n) {
            if (m < 0 || n < 0) return -1;
            if ((m == 0 && n == 0) || index >= strs.length) return 0;
            //防止无线循环
//            if (handle[index][m][n] != 0) {
//                return handle[index][m][n];
//            }
            int zeroes = countZeros.apply(strs[index]);
            int ones = strs[index].length() - zeroes;
            int count1 = maxForm(strs, index + 1, m, n);
            int count2 = maxForm(strs, index + 1, m - zeroes, n - ones) + 1;
//            System.out.println("index: " + index + "\tm = " + m + "\t n = " + n + "\t count1: " + count1 + "\t count2: " + count2 + "\t result:" + Math.max(count1, count2));
            handle[index][m][n] = Math.max(count1, count2);
            return handle[index][m][n];
        }

    }

    static class Solution2 {

        public int findMaxForm(String[] strs, final int m, final int n) {
            int[][] dp = new int[m + 1][n + 1];
            Function<String, Integer> countZeros = s -> {
                int count = 0;
                for (int i = 0; i < s.length(); ++i) {
                    if (s.charAt(i) == '0') {
                        ++count;
                    }
                }
                return count;
            };
            for (int i = 0; i < strs.length; i++) {
                int zeros = countZeros.apply(strs[i]);
                int ones = strs[i].length() - zeros;
                for (int j = m; j >= zeros; --j) {
                    for (int k = n; k >= ones; --k) {
                        dp[j][k] = Math.max(dp[j][k], 1 + dp[j - zeros][k - ones]);
                    }
                }
            }
            return dp[m][n];
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] cases = new String[]{"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
//        int result = solution.findMaxForm(cases, m, n);
        int result = 0;
        //System.out.println(result + "\t");
        cases = new String[]{"11", "11", "0", "0", "10", "1", "1", "0", "11", "1", "0", "111", "11111000", "0", "11", "000", "1", "1", "0", "00", "1", "101", "001", "000", "0", "00", "0011", "0", "10000"};
        m = 90;
        n = 66;
        result = solution.findMaxForm(cases, m, n);
        System.out.println(result + "\t");
    }
}
